﻿//
//class sum
//{
//public:
//    sum()
//    {
//        _ret += _i;
//        _i++;
//    }
//
//    static int Getret()
//    {
//        return _ret;
//    }
//
//private:
//    static int _i;
//    static int _ret;
//
//};
//
//int sum::_i = 1;
//int sum::_ret = 0;
//
//
//class Solution {
//public:
//    int Sum_Solution(int n) {
//        sum* p = new sum[n];
//        return sum::Getret();
//    }
//};



//
//#define _CRT_SECURE_NO_WARNINGS 1
//#include <iostream>
//using namespace std;
//
//
//class Date
//{
//public:
//    int Get_day(int year, int month)
//    {
//        int month_day[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//        if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
//        {
//            month_day[2] = 29;
//        }
//        return month_day[month];
//    }
//
//    Date(int year, int month, int day)
//        :_year(year)
//        , _month(month)
//        , _day(day)
//    {
//    }
//
//    bool operator<(const Date& d)
//    {
//        if (_year < d._year)
//        {
//            return true;
//        }
//        else
//        {
//            if (_month < d._month)
//            {
//                return true;
//            }
//            else
//            {
//                if (_day < d._day)
//                {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//    bool operator==(const Date& d)
//    {
//        return _year == d._year
//            && _month == d._month
//            && _day == d._day;
//    }
//    bool operator!=(const Date& d)
//    {
//        return !(*this == d);
//    }
//
//    Date& operator-=(int day)
//    {
//        if (day < 0)
//        {
//            return *this += (-day);
//        }
//        _day -= day;
//        while (_day <= 0)
//        {
//            _month--;
//            if (_month == 0)
//            {
//                _year--;
//                _month = 12;
//            }
//            _day += Get_day(_year, _month);
//        }
//        return *this;
//
//    }
//
//    Date& operator+=(int day)
//    {
//        if (day < 0)
//        {
//            return *this -= (-day);
//        }
//        _day += day;
//
//        _day += day;
//        if (_day > Get_day(_year, _month))
//        {
//            _day -= Get_day(_year, _month);
//            _month++;
//            if (_month == 13)
//            {
//                _year++;
//                _month = 1;
//            }
//        }
//        return *this;
//    }
//
//
//    Date operator++()
//    {
//        Date tmp = *this;
//        *this += 1;
//        return tmp;
//    }
//
//    Date operator++(int)
//    {
//        Date tmp = *this;
//        *this += 1;
//        return tmp;
//    }
//
//    void get_monthday(const Date& d)
//    {
//
//        Date max = *this;
//        Date min = d;
//        if (*this < d)
//        {
//            max = d;
//            min = *this;
//
//        }
//
//        int day = 0;
//        while (max != min)
//        {
//            min++;
//            day++;
//        }
//        day++;
//        cout << day << endl;
//
//    }
//private:
//    int _year;
//    int _month;
//    int _day;
//
//};
//int main() {
//    int year1, year2, month1, month2, day1, day2;
//    scanf("%4d%2d%2d", &year1, &month1, &day1);
//    scanf("%4d%2d%2d", &year2, &month2, &day2);
//    Date d1(year1, month1, day1);
//    Date d2(year2, month2, day2);
//    d1.get_monthday(d2);
//
//
//}


//#include <iostream>
//using namespace std;
//
//int main() {
//    int _year, _month, _day;
//    int month_day[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//    cin >> _year >> _month >> _day;
//    if ((_year % 4 == 0 && _year % 100 != 0) || (_year % 400 == 0))
//    {
//        month_day[2] = 29;
//    }
//    int ret = 0;
//    for (int i = 0; i < _month; i++)
//    {
//        ret += month_day[i];
//    }
//    ret += _day;
//    cout << ret;
//
//}
//#define _CRT_SECURE_NO_WARNINGS 1
//
//#include <iostream>
//using namespace std;
//
//bool islearyear(int year)
//{
//    return ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0);
//}
//int main() {
//    int month_day[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//    int m, year, month = 0, day, number = 0;
//    cin >> m;
//    while (scanf("%d%d", &year, &number) != EOF)
//    {
//        while (number > month_day[month])
//        {
//            if (islearyear(year))
//            {
//                return month_day[2] = 29;
//            }
//            else {
//                return month_day[2] = 28;
//            }
//            number -= month_day[month];
//            month++;
//            // if(month==13)
//            // {
//            //     year++;
//            //     month=1;
//            // }
//        }
//        printf("%04d-%02d-%02d\0", year, month, number);
//    }
//    return 0;
//}
#include<stdlib.h>
#include<iostream>
using namespace std;
//int globalVar = 1;
//
//static int staticGlobalVar = 1;
//
//int main()
//
//{
//
//	static int staticVar = 1;
//
//	int localVar = 1;
//
//
//
//	int num1[10] = { 1, 2, 3, 4 };//40
//
//	char char2[] = "abcd";//5 4
//
//	const char* pChar3 = "abcd";
//
//	int* ptr1 = (int*)malloc(sizeof(int) * 4);
//
//	int* ptr2 = (int*)calloc(4, sizeof(int));
//
//	int* ptr3 = (int*)realloc(ptr2, sizeof(int) * 4);
//
//	free(ptr1);//16
//
//	free(ptr3);
//	cout << sizeof(num1) << endl;
//	cout << sizeof(char2) << strlen(char2)<< endl;
//	cout << sizeof(pChar3) << strlen(pChar3) << endl;
//	cout << sizeof(ptr1) << endl;
//}


//反转字符串 II
//class Solution {
//public:
//    string reverseStr(string s, int k) {
//        for (int i = 0; i < s.size(); i += 2 * k)
//        {
//            if (i + k < s.size())
//            {
//                reverse(s.begin() + i, s.begin() + i + k);
//                continue;
//            }
//            reverse(s.begin() + i, s.end());
//        }
//        return s;
//    }
//};

//验证回文串
//class Solution {
//public:
//    bool itletter(char ch)
//    {
//        if (ch >= '0' && ch <= '9')
//            return true;
//        if (ch >= 'a' && ch <= 'z')
//            return true;
//        if (ch >= 'A' && ch <= 'Z')
//            return true;
//
//        return false;
//    }
//    bool isPalindrome(string s) {
//        //    string::iterator it = s.begin();
//        //    while(it != s.end())
//        //    {
//
//        //         if(*it >= 'a' && *it <= 'z')
//        //         *it -= 32;
//        //          it++;
//        //    }
//
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (s[i] >= 'a' && s[i] <= 'z')
//                s[i] -= 32;
//        }
//
//        // for(auto& it : s)
//        // {
//        //     if(it >= 'a' && it <= 'z')
//        //          it -= 32;
//        // }
//
//        int left = 0, right = s.size() - 1;
//        while (left < right)
//        {
//            while (left < right && !itletter(s[left]))
//                left++;
//            while (left < right && !itletter(s[right]))
//                right--;
//            if (s[left] != s[right])
//            {
//                return false;
//            }
//            else
//                ++left, --right;
//
//        }
//        return true;
//    }
//};

//字符串最后一个单词的长度
//#include <iostream>
//using namespace std;
//
//int main() {
//    string str;
//    while (getline(cin, str))
//    {
//        int pos = str.rfind(" ");
//        cout << str.size() - pos - 1 << endl;
//    }
//
//}

//反转字符串
//class Solution {
//public:
//    void reverseString(vector<char>& s) {
//        int right = s.size() - 1;
//        for (int left = 0; left < right; ++left, --right)
//        {
//            swap(s[left], s[right]);
//        }
//    }
//};

//字符串相加
//class Solution {
//public:
//    string addStrings(string num1, string num2) {
//        string str1;
//        int end1 = num1.size() - 1;
//        int end2 = num2.size() - 1;
//        int n1 = 0, n2 = 0, next = 0;
//        while (end1 >= 0 || end2 >= 0)
//        {
//            n1 = end1 >= 0 ? num1[end1--] - '0' : 0;
//            n2 = end2 >= 0 ? num2[end2--] - '0' : 0;
//            int ret = n1 + n2 + next;
//            next = ret / 10;
//            ret = ret % 10;
//            str1 += (ret + '0');
//        }
//
//        if (next == 1)
//            str1 += '1';
//        reverse(str1.begin(), str1.end());
//        return str1;
//    }
//};

//把字符串转换成整数 (atoi)
#include<climits>
class Solution {
public:
    int myAtoi(string s) {


        int flag = 1;
        int idx = 0;
        int size = s.size();
        while (idx < size)
        {
            if (s[idx] == ' ')
            {
                idx++;
            }
            else
                break;
        }
        if (idx == size)
            return 0;
        if (s[idx] == '+')
            idx++;
        else if (s[idx] == '-')
        {
            idx++;
            flag = -1;
        }
        if (idx == size)
            return 0;

        int sum = 0;
        while (idx < size)
        {
            if (s[idx] < '0' || s[idx]>'9')
                break;

            if (sum > INT_MAX / 10 || (sum == INT_MAX / 10 && (s[idx] - '0') >= (INT_MAX % 10)))
                return INT_MAX;
            if (sum < INT_MIN / 10 || (sum == INT_MIN / 10 && (s[idx] - '0') >= -(INT_MIN % 10)))
                return INT_MIN;

            sum = sum * 10 + flag * (s[idx] - '0');
            idx++;
        }
        return sum;
    }
};